#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cassert>

#include "gtest/gtest.h"

static const int N = 100;

// Самопальный класс, реализующий хранение строки более менее
// эффективным образом с точки зрения копирования.
class String {
 public:
  // "explicit" запрещает неявное приведение аргумента, что мы
  // могли точно знать, какие конструктор каких классов вызываются.
  explicit String(const std::string& value) { 
    init(value.c_str(), value.length()); 
  }
  String(const String& value) { init(value.data_, value.sz_); }
  ~String() { free(data_); }

  // Данный оператор - это, пожалуй, единственная попытка сделать
  // работу с памятью эффективной.
  String& operator=(const String& value) {
    if (this != &value) {
      // Память перераспределяется только если оригинал длинее текущей
      // строки. Ясно, что при такой реализации строка может только
      // расти в плане занимаемой памяти.
      if (value.sz_ > sz_) data_ = (char*)std::realloc(data_, value.sz_);
      sz_ = value.sz_;
      std::memcpy(data_, value.data_, sz_);
    }
    return *this;
  }

  friend class StringCmp;
  friend class StringPointerCmp;

 private:
  void init(const char* data, size_t sz) {
    sz_ = sz;
    data_ = (char*)malloc(sz_);
    std::memcpy(data_, data, sz_);
  }
  char* data_;
  size_t sz_;
};

std::vector<std::string> std_strings;
std::vector<std::string*> std_strings_p;
std::vector<String> strings;
std::vector<String*> strings_p;

// Объект для сравнения двух std::string.
class StlStringCmp {
 public:
  bool operator()(const std::string& a, const std::string& b) {
    return a < b;
  }
};

TEST(SortingStlString, StlString) {
  std::sort(std_strings.begin(), std_strings.end(), StlStringCmp());
}

// Объект для сравнения двух std::string*.
class StlStringPointerCmp {
 public:
  bool operator()(const std::string* a, const std::string* b) {
    return *a < *b;
  }
};

TEST(SortingStlString, StlStringPointer) {
  std::sort(std_strings_p.begin(), std_strings_p.end(), StlStringPointerCmp());
}

// Объект для сравнения двух String.
class StringCmp {
 public:
  bool operator()(const String& a, const String& b) {
    assert(a.sz_ == b.sz_);
    return std::memcmp(a.data_, b.data_, a.sz_);
  }
};

TEST(SortingStlString, String) {
  std::sort(strings.begin(), strings.end(), StringCmp());
}

// Объект для сравнения двух String*.
class StringPointerCmp {
 public:
  bool operator()(const String* a, const String* b) {
    assert(a->sz_ == b->sz_);
    return std::memcmp(a->data_, b->data_, a->sz_);
  }
};

TEST(SortingStlString, StringPointer) {
  std::sort(strings_p.begin(), strings_p.end(), StringPointerCmp());
}

int main(int argc, char* argv[]) {
  // Это наполнитель, чтобы строки были длинные, и копирование было
  // ощутимо дорого.
  std::string big(1024 * 1024, '?');
  for (int i = 0; i < N; ++i) {
    // Все строки будут одинаковой длины. Функции сравнения рассчитывают
    // на это.
    std::stringstream fmt;
    fmt << N * 2 - i << big;
    // std::string строка-объект.
    std_strings.push_back(fmt.str());
    // std::string строка-указатель.
    std_strings_p.push_back(new std::string(fmt.str()));
    // Моя строка-объект.
    strings.push_back(String(fmt.str()));
    // Моя строка-указатель.
    strings_p.push_back(new String(fmt.str()));
  }

  testing::InitGoogleTest(&argc, argv);
  // Принудительно печатаем время работы тестов.
  testing::GTEST_FLAG(print_time) = true;
  return RUN_ALL_TESTS();
}
